﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = IsHappy(100);
            Console.WriteLine(result);
            Console.ReadKey();
        }

        #region 202.快乐数(未完成)
        /// <summary>
        /// 判断一个数是否为快乐数
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static bool IsHappy(int n)
        {
            HashSet<int> set = new HashSet<int>();
            while (n != 1)
            {
                n = n.ToString().Select(x => Convert.ToInt32(x.ToString())).Sum(x => x * x);
                if (set.Contains(n))
                {
                    return false;
                }
                set.Add(n);
            }
            return true;

        }
        #endregion


        #region 190. 颠倒二进制位
        /// <summary>
        /// 关键思路:位运算
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static uint reverseBits(uint n)
        {
            long a = 0;
            for (int i = 0; i <= 31; i++)
            {
                a = a + ((1 & (n >> i)) << (31 - i));
            }
            return (uint)a;
        }
        #endregion
        #region 168.Excel表列名称
        /// <summary>
        /// 给定一个数字，返回EXCEL的表列名称
        /// </summary>
        /// <param name="columnNumber"></param>
        /// <returns></returns>
        public static string ConvertToTitle(int columnNumber)
        {
            //把数字转换成26进制，然后匹配对应的字母即可。
            //65-90--->A-Z
            string s = string.Empty;
            while (columnNumber > 0)
            {
                int m = columnNumber % 26;
                if (m == 0)
                {
                    m = 26;
                }
                s = (char)(m + 64) + s;
                columnNumber = (columnNumber - m) / 26;
            }
            return s;
        }
        #endregion
        #region 167. 两数之和 II - 输入有序数组
        /// <summary>
        /// 两数之和 II - 输入有序数组
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static int[] TwoSum(int[] numbers, int target)
        {
            var result = new int[2];
            int left = 0;
            int right = numbers.Length - 1;
            while (left<right)
            {
                if (numbers[left] + numbers[right] == target)
                {
                    result[0] = ++left;
                    result[1] = ++right;
                    break;
                }
                else if (numbers[left] + numbers[right] < target)
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
            return result;
        }
        #endregion
        #region 136. 只出现一次的数字
        public static int SingleNumber(int[] nums)
        {
            #region 方法1 排序之后比较
            //思路
            //1.先排序
            //2.定义一个索引，比较当前值和左边的值以及当前值和右边的值，
            //3.若都不一样，则只出现一次。
            //int index = 0;
            //int result = nums[0];
            //Array.Sort(nums);
            //while (index < nums.Length - 1)
            //{
            //    if (index == 0)
            //    {
            //        if (nums[index] != nums[index + 1])
            //        {
            //            result = nums[index];
            //            break;
            //        }
            //    }
            //    else
            //    {
            //        if ((nums[index] != nums[index - 1]) && (nums[index] != nums[index + 1]))
            //        {
            //            result = nums[index];
            //            break;
            //        }
            //        else
            //        {
            //            result = nums[index + 1];
            //        }
            //    }
            //    index++;

            //}
            //return result;
            #endregion

            #region 方法2 异或运算
            //把值转成二进制，相同为0不同为1，
            for (int i = 1; i < nums.Length; i++)
            {
                nums[0] ^= nums[i];
            }
            return nums[0];
            #endregion
        }
        #endregion
        # region 125.验证回文串
        public static bool IsPalindrome(string s)
        {
            //思路
            //1.循环左右比较是否相同
            //2.如果遇到非字母和数字则需要跳过，继续比较下一个字符
            bool flag = true;
            string str = s.ToLower();
            int left = 0;
            int right = str.Length-1;
            while ((left != right) &&(left<right))
            {
                bool strOrNumber1 = false;
                bool strOrNumber2 = false;
                var s1 = str[left];
                var s2 = str[right];
                if (char.IsLetter(s1) || char.IsNumber(s1))
                {
                    strOrNumber1 = true;
                }
                else
                {
                    left++;
                }
                if (char.IsLetter(s2) || char.IsNumber(s2))
                {
                    strOrNumber2 = true;
                }
                else
                {
                    right--;
                }
                if (strOrNumber1 && strOrNumber2)
                {
                    if (str[left] != str[right])
                    {
                        flag = false;
                    }
                    left++;
                    right--;
                }
            }
            return flag;
        }
        #endregion
        #region 119.杨辉三角 II
        public static IList<int> GetRow(int rowIndex)
        {
            rowIndex++;
            IList<IList<int>> allArrs = new List<IList<int>>();
            allArrs.Add(new List<int> { 1 });
            if (rowIndex > 1)
            {
                for (int i = 1; i < rowIndex; i++)
                {
                    IList<int> list = new List<int>();
                    for (int j = 0; j <= i; j++)
                    {
                        int left = 0;
                        int right = 0;
                        if (j - 1 >= 0)
                        {
                            left = allArrs[i - 1][j - 1];
                        }
                        if (j <= allArrs[i - 1].Count - 1)
                        {
                            right = allArrs[i - 1][j];
                        }
                        int number = left + right;
                        list.Add(number);
                    }
                    allArrs.Add(list);
                }
            }
            return allArrs[rowIndex-1];
        }
        #endregion
        #region 118.杨辉三角
        public static IList<IList<int>> Generate(int numRows)
        {
            IList<IList<int>> result = new List<IList<int>>();
            result.Add(new List<int> { 1 });
            if (numRows > 1)
            {
                for (int i = 1; i < numRows; i++)
                {
                    IList<int> list = new List<int>();
                    for (int j = 0; j <= i; j++)
                    {
                        int left = 0;
                        int right = 0;
                        if (j - 1 >= 0)
                        {
                            left = result[i - 1][j - 1];
                        }
                        if (j <= result[i - 1].Count - 1)
                        {
                            right = result[i - 1][j];
                        }
                        int number = left + right;
                        list.Add(number);
                    }
                    result.Add(list);
                }
            }
            return result;
        }
        #endregion
        #region 104.二叉树的最大深度(未完成)
        public static int MaxDepth(TreeNode root)
        {
            int depth = 0;
            if (root==null)
            {
                depth = 0;
            }
            if (root.left !=null || root.right!=null)
            {
                depth++;
                DepthChildren(root, ref depth);
            }
            else
            {
                depth = 1;
            }
            return depth;
        }
        public static void DepthChildren(TreeNode p, ref int depth)
        {
            if (p.left != null)
            {
                depth++;
                DepthChildren(p.left, ref depth);
            }
            if (p.right!=null)
            {
                depth++;
                DepthChildren(p.right, ref depth);
            }

        }

        #endregion
        #region 101.对称二叉树
        // var root = new TreeNode() { val=1, left=new TreeNode() { val=2 }, right=new TreeNode() { val=2 } };
        public static bool IsSymmetric(TreeNode root)
        {
            if (root==null)
            {
                return true;
            }
            if (root.left == null && root.right==null)
            {
                return true;
            }
            if (root.left !=null && root.right!=null && root.left.val==root.right.val)
            {
                return IsSymmetricChildren(root.left, root.right);
            }
            else
            {
                return false;
            }
        }

        public static bool IsSymmetricChildren(TreeNode p, TreeNode q)
        {
            if (p == null && q == null)
            {
                return true;
            }
            if (p == null || q == null || p.val != q.val)
            {
                return false;
            }
            return IsSymmetricChildren(p.left, q.right) && IsSymmetricChildren(p.right, q.left);
        }
        #endregion
        #region 100.相同的数
        /* 
        var p = new TreeNode() { val=1,left=new TreeNode() { val=2},right=new TreeNode() { val=3} };
        var q = new TreeNode() { val=1, left=new TreeNode() { val=2 }, right=new TreeNode() { val=3 } };
        var result = IsSameTree(p, q);
        */
        public static bool IsSameTree(TreeNode p, TreeNode q)
        {
            if (p==null && q==null)
            {
                return true;
            }
            if (p==null || q == null)
            {
                return false;
            }
            if (p.val==q.val)
            {
                return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
            }
            else
            {
                return false;
            }

        }
        #endregion
        #region 94. 二叉树的中序遍历
        /// <summary>
        /// 二叉树的中序遍历
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static IList<int> InorderTraversal(TreeNode root)
        {
            //中序遍历的顺序为左根右
            var result = new List<int>();
            //Stack堆栈，后进先出的规则
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode cur = root;
            while (cur!=null || !(stack.Count == 0))
            {
                if (cur != null)
                {
                    stack.Push(cur);
                    cur = cur.left;
                }
                else
                {
                    cur = stack.Pop();
                    result.Add(cur.val);
                    cur = cur.right;
                }
            }
            return result;
        }
        #endregion
        #region 29. 两数相除(未完成,减法超时)
        public static int Divide(int dividend, int divisor)
        {
            int maxValue = int.MaxValue-1;
            int minValue = int.MinValue;
            int index = 0;
            //默认是负数
            int negativeCount = 0;
            bool over = false;
            if (dividend==0)
            {
                return 0;
            }
            //被除数小于0
            if (dividend<0)
            {
                int a = 0;
                try
                {
                    a = dividend<minValue ? maxValue : Math.Abs(dividend);
                }
                catch (Exception)
                {
                    over =true;
                    a = maxValue;
                }

                dividend = a;
                negativeCount++;
            }
            if (divisor<0)
            {
                int a = 0;
                try
                {
                    a= divisor<minValue ? maxValue : Math.Abs(divisor);
                }
                catch (Exception)
                {
                    a = maxValue;
                }

                divisor =a;
                negativeCount++;
            }
            int rest = dividend;
            while (rest >= divisor)
            {
                rest = rest - divisor;
                index++;
            }
            if (negativeCount==1)
            {
                if (over)
                {
                    index = (index*-1)-1;
                }
                else
                {
                    index = index*-1;
                }
            }
            return index;
        }
        #endregion
        #region 17. 电话号码的字母组合
        public static IList<string> LetterCombinations(string digits)
        {
            //队列法
            List<string> result = new List<string>();
            List<string[]> letters = new List<string[]> {
                new string[] { "a", "b", "c" },
                new string[] { "d", "e", "f" },
                new string[] { "g", "h", "i" },
                new string[] { "j", "k", "l" },
                new string[] { "m", "n", "o" },
                new string[] { "p", "q", "r", "s" },
                new string[] { "t", "u", "v" },
                new string[] { "w", "x", "y", "z" } };
            char[] chars = digits.ToCharArray();
            //第一个数字对应的字母全部放到队列中
            if (chars.Length > 0)
            {
                var number = int.Parse(chars[0].ToString());
                result = letters[number-2].ToList<string>();
            }
            //循环数字
            for (int i = 1; i < chars.Length; i++)
            {
                var number = int.Parse(chars[i].ToString());
                //找到数字对应的字母
                var letter = letters[number-2].ToList<string>();
                var count = result.Count;
                //重点来了，循环第一个数字对应的m个字母
                for (int m = 0; m < count; m++)
                {
                    //累加后面数字的每一个字母
                    var first = result[0];
                    for (int j = 0; j < letter.Count; j++)
                    {
                        result.Add(first+letter[j]);
                    }
                    //移除第一位置的字母
                    result.RemoveAt(0);
                }
            }
            return result;
        }
        #endregion
        #region 11. 盛最多水的容器
        public static int MaxArea(int[] height)
        {
            if (height.Length==2)
            {
                return 1*Math.Min(height[0], height[1]);
            }
            int left = 0;
            int right = height.Length-1;
            int maxArea = 0;
            while (left<right)
            {
                int area = (right-left)* Math.Min(height[left], height[right]);
                if (height[left]<height[right])
                {
                    left++;
                }
                else if (height[left]>height[right])
                {
                    right--;
                }
                else
                {
                    left++;
                    right--;
                }

                maxArea= maxArea>area ? maxArea : area;
            }
            return maxArea;
        }
        #endregion 
        #region 8. 字符串转换整数 (atoi)
        public static int MyAtoi(string s)
        {
            //是不是负数
            bool negative = false;
            s=s.Trim();
            List<string> list = new List<string>();
            char[] chars = s.ToCharArray();
            for (int i = 0; i < chars.Length; i++)
            {
                if (i==0)
                {
                    if (chars[0].ToString()=="-")
                    {
                        negative = true;
                        continue;
                    }
                    if (chars[0].ToString()=="+")
                    {
                        negative = false;
                        continue;
                    }
                    if (chars[0].ToString()==".")
                    {
                        break;
                    }
                    if (char.IsNumber(chars[i]))
                    {
                        list.Add(chars[i].ToString());
                        continue;
                    }
                    if (!char.IsNumber(chars[i]))
                    {
                        break;
                    }
                }
                else
                {
                    if (char.IsNumber(chars[i]))
                    {
                        list.Add(chars[i].ToString());
                    }
                    else
                    {
                        break;
                    }
                }
            }
            var cc = string.Join("", list);
            var result = 0;
            bool isMax = false;
            if (cc.Length==0)
            {
                return result;
            }
            try
            {
                result = Convert.ToInt32(cc);
            }
            catch (Exception)
            {
                result = int.MaxValue;
                isMax = true;
            }

            if (negative)
            {
                result = result*-1;
                if (isMax)
                {
                    result--;
                }
            }
            return result;
        }
        #endregion
        #region 7. 整数反转
        public static int Reverse(int x)
        {
            bool negative = false;
            string str = x.ToString();
            if (str.Length==1)
            {
                return x;
            }
            if (str.StartsWith("-")==true)
            {
                str = str.Substring(1);
                negative=true;
            }
            char[] chars = str.ToCharArray();
            long result = 0;
            var b = chars.Length;
            for (int i = chars.Length-1; i >=0; i--)
            {
                long a = Convert.ToInt32(chars[i].ToString());
                b--;
                long c = (long)Math.Pow(10, b);
                result+=a*c;
            }
            if (negative)
            {
                result = result*-1;
            }
            //注意int32 长度是到2的31次方，约十亿左右。
            result = result>(long)(Math.Pow(2, 31)-1) ? 0 : result;
            result = result<-(long)Math.Pow(2, 31) ? 0 : result;

            return Convert.ToInt32(result);
        }
        #endregion
        #region 5. 最长回文子串
        public void Start()
        {
            var s1 = "abba";
            var s2 = "nypdmqqgauepeyfvwcdpbmmaxfwxmmtswfuwldtvqcisywalfnvovuordczxlyzqmslxilpnenbuwbcpebneovitwkkswsijajnkwkfbxnulmwotgrmpklntfyjavccbrgwqynryeoswmhsqzcwnudkuvfkikjxjkjpghsytjfkpvkjpvblamdeegeohospporbtorkbuggbawgodhxpscfksjbirxvjyjapwwushmnqsxktnslvonlwvuseinrmwvfqjgzpkwcqfzfdbbmcngmsoeegudwjvldqmaomwbqvijesnpxiqvtfeiqebrfjhtvjdwkopyfzaslewdjnkmalvfinbuouwcgnfecjtdzwycxrynxepbcsroyzrsgiiuaszvatwyuxinwhni";
            var result = LongestPalindromeA(s2);
        }
        //中心扩散法
        public static string LongestPalindrome(string s)
        {
            //从左边第一个字符开始，向两边扩散，记录下最长的回文子串
            int len = s.Length;
            int longestLen = 0;
            if (len==1)
            {
                return s;
            }
            char[] chars = s.ToCharArray();
            int left = 0;
            int right = 0;
            for (int i = 0; i < len; i++)
            {
                int subLeft = i;
                int subRight = i;
                //查找中心点
                while (subRight+1<len&&chars[i]==chars[subRight+1])
                {
                    subRight++;
                }
                //左右扩散
                while (subRight+1<len&&subLeft-1>=0&&chars[subLeft-1]==chars[subRight+1])
                {
                    subLeft--;
                    subRight++;
                }
                int length = subRight-subLeft;
                if (length>longestLen)
                {
                    left = subLeft;
                    right = subRight;
                    longestLen = length;
                }
            }
            return s.Substring(left, right-left+1);
        }


        //逻辑正常，但是超时
        //思路：从最大长度，一直减少，直到找到一个回文子串为止
        public static string LongestPalindromeA(string s)
        {
            int len = s.Length;
            string longestStr = "";
            if (len==1)
            {
                return s;
            }
            int length = len;
            while (length>0)
            {
                for (int i = 0; i < len; i++)
                {
                    if (i+length>len)
                    {
                        break;
                    }
                    var newStr = s.Substring(i, length);
                    var isp = IsPalindromeA(newStr);
                    if (isp)
                    {
                        longestStr = longestStr.Length>newStr.Length ? longestStr : newStr;
                        break;
                    }
                }
                length--;
                if (longestStr!="")
                {
                    break;
                }
            }
            return longestStr;
        }
        public static bool IsPalindromeA(string str)
        {
            bool flag = true;
            int left = 0;
            int right = str.Length-1;
            while ((left != right) &&(left<right))
            {
                if (str[left] != str[right])
                {
                    flag = false;
                }
                left++;
                right--;
            }
            return flag;
        }
        #endregion
        #region 3. 无重复字符的最长子串
        public static int LengthOfLongestSubstring(string s)
        {
            char[] chars = s.ToCharArray();
            int len = chars.Length;
            int index = 0;
            int longest = 0;
            if (chars.Length==1)
            {
                return 1;
            }
            while (index <len)
            {
                var newLen = 0;
                var cs = new List<char>();
                for (int i = index; i < len; i++)
                {
                    if (!cs.Contains(chars[i]))
                    {
                        newLen++;
                        cs.Add(chars[i]);
                    }
                    else
                    {
                        index++;
                        break;
                    }
                    if (i==(len-1))
                    {
                        index = len;
                    }
                    longest = longest>newLen ? longest : newLen;
                }
            }
            return longest;
        }
        #endregion
        #region 2.两数相加
        public static ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            var result = new List<int>();
            var ten = 0;
            return AddTwoNumbersA(l1, l2, ref result, ref ten);
        }
        public static void PrintResult(ListNode result)
        {
            Console.Write(result.val+" ");
            if (result.next!=null)
            {
                PrintResult(result.next);
            }
        }
        public static ListNode AddTwoNumbersA(ListNode l1, ListNode l2, ref List<int> result, ref int ten)
        {
            var left = l1;
            var right = l2;
            if (left !=null)
            {
                left = l1;
            }
            if (right!=null)
            {
                right = l2;
            }

            var realnumber = left.val+right.val;
            var number = realnumber;
            if (realnumber>=10)
            {
                number = realnumber-10;
            }
            if (ten == 1)
            {
                var num = number+1;
                if (num>=10)
                {
                    num = num-10;
                    result.Add(num);
                    var node1 = l1.next!=null ? l1.next : new ListNode();
                    var node2 = l2.next!=null ? l2.next : new ListNode();
                    return AddTwoNumbersA(node1, node2, ref result, ref ten);
                }
                else
                {
                    result.Add(num);
                }
            }
            else
            {
                result.Add(number);
            }
            ten = realnumber>=10 ? 1 : 0;
            if (l1.next==null && l2.next==null)
            {
                if (ten==1)
                {
                    var node1 = l1.next!=null ? l1.next : new ListNode();
                    var node2 = l2.next!=null ? l2.next : new ListNode();
                    return AddTwoNumbersA(node1, node2, ref result, ref ten);
                }
                var resNode = new ListNode();
                var index = 0;
                FillNode(result, ref index, ref resNode);
                return resNode;
            }
            else
            {
                var node1 = l1.next!=null ? l1.next : new ListNode();
                var node2 = l2.next!=null ? l2.next : new ListNode();

                return AddTwoNumbersA(node1, node2, ref result, ref ten);
            }
        }
        public static ListNode FillNode(List<int> list, ref int index, ref ListNode ln)
        {
            if (index == list.Count)
            {
                return ln;
            }
            if (ln==null)
            {
                ln = new ListNode(list[index]);
            }
            else
            {
                ln.val = list[index];
            }
            index++;
            return FillNode(list, ref index, ref ln.next);
        }
        #endregion
        
    }

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }
}
